import java.util.Deque;
import java.util.LinkedList;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网:BM44 有效括号序列
 * <a href="https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=295&tqId=726&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2023-03-12
 * Time: 23:43
 */

public class Solution {
    //本题的另一种解题思路是每次匹配到左括号时,将对应的右括号压入栈中
    //之后若是右括号只需要检验栈的pop字符和ch字符相等即可
    public boolean isValid (String s) {
        //辅助栈
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
                continue;
            }
            if (stack.isEmpty()) {
                return false;
            }
            int ch2 = stack.pop();
            if ((ch == ')' && ch2 != '(')
                    || (ch == ']' && ch2 != '[')
                    || (ch == '}' && ch2 != '{')) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
